//
// Created by SunYing on 2017/11/2.
//

#include <iostream>
#include "SortTestHelper.h"
#include "SelectionSort.h"

using namespace std;

template<typename T>
void insertionSort(T arr[], int n) {
//  从1开始往后分配地址
    for (int i = 1; i < n; ++i) {
        // 保存第当前循环到的变量i
        T e = arr[i];
        // j 保存元素e应该插入的位置
        int j;
//         从i的位置开始往前开始比较,如果说它前一个的数值比当前的i的下标的值要大,那么就呼唤当前的值和它
//        前一个的值
        for (j = i; j > 0 && arr[j - 1] > e; --j) {
            arr[j] = arr[j - 1];
        }
        arr[j] = e;
    }
    return;
}

int main() {
    int n = 20000;

//  一般性测试
    cout << "Test for random array, size = " << n << ", random range [0," << n << "]" << endl;
    int *arr1 = SortTestHelper::generateRandomArray(n, 0, n);
    int *arr2 = SortTestHelper::copyIntArray(arr1, n);

    SortTestHelper::testSort("Insertion Sort", insertionSort, arr1, n);
    SortTestHelper::testSort("Selection Sort", selectionSort, arr2, n);

    delete[] arr1;
    delete[] arr2;

    cout << endl;

//    有序性测试
    cout << "Test for more ordered random array, size = " << n << ", random range[0, 3]" << endl;
    arr1 = SortTestHelper::generateRandomArray(n, 0, 3);
    arr2 = SortTestHelper::copyIntArray(arr1, n);

    SortTestHelper::testSort("Insertion Sort", insertionSort, arr1, n);
    SortTestHelper::testSort("Selection Sort", selectionSort, arr2, n);

    delete[] arr1;
    delete[] arr2;

    cout << endl;

// 测试近乎有序的数组
    int swapTimes = 100;
    cout << "Test for nearly ordered array, size = " << n << ", swap time = " << swapTimes << endl;
    arr1 = SortTestHelper::generateNearlyOrderedArray(n, swapTimes);
    arr2 = SortTestHelper::copyIntArray(arr1, n);

    SortTestHelper::testSort("Insertion Sort", insertionSort, arr1, n);
    SortTestHelper::testSort("Selection Sort", selectionSort, arr2, n);

    delete[] arr1;
    delete[] arr2;

    return 0;
}